import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();

        int n = nums.length;
        for (int a = 0; a < n;){
            List<List<Integer>> res = threeSum(nums, a, target);
            ret.add(new ArrayList(res));

            a++;
            while (a < n && nums[a] == nums[a - 1]){
                a++;
            }
        }

        return ret;
    }

    public List<List<Integer>> threeSum (int[] nums, int a, int target){
        List<List<Integer>> ret = new ArrayList<>();

        int n = nums.length;
        for (int b = a + 1; b < n;){
            int left = b + 1;
            int right = n - 1;

            while (left < right){
                int sum = nums[left] + nums[right];
                if (sum < target - nums[b] - nums[a]){
                    left++;
                }else if (sum > target - nums[b] - nums[a]){
                    right--;
                }else{
                    ret.add(new ArrayList(Arrays.asList(nums[a], nums[b], nums[left], nums[right])));

                    right--;
                    left++;
                    while (left < right && nums[left] == nums[left - 1]){
                        left++;
                    }

                    while (left < right && nums[right] == nums[right + 1]){
                        right--;
                    }

                }
            }

            b++;
            while (b < n && nums[b] == nums[b - 1]){
                b++;
            }
        }

        return ret;
    }

    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int n = nums.length;
        int len = Integer.MAX_VALUE;

        for (int left = 0, right = 0; right < n; right++){
            sum += nums[right];

            while (sum >= target){
                len = Math.min(len, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return len == Integer.MAX_VALUE? 0 : len;
    }

    public static void main(String[] args) {
        Solution test = new Solution();
        test.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);
    }
}
